package com.yubest;

/**
 * 给你一个整数数组 nums ，请你找出数组中乘积最大的连续子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。
 * <p>
 *  
 * <p>
 * 示例 1:
 * <p>
 * 输入: [2,3,-2,4]
 * 输出: 6
 * 解释: 子数组 [2,3] 有最大乘积 6。
 * 示例 2:
 * <p>
 * 输入: [-2,0,-1]
 * 输出: 0
 * 解释: 结果不能为 2, 因为 [-2,-1] 不是子数组。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/maximum-product-subarray
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 *
 * @Author hweiyu
 * @Description
 * @Date 2021/12/28 14:16
 */
public class P0152 {

    public static void main(String[] args) {
        new Solution152().maxProduct(new int[]{-1, 0, -1});

        new Solution152().maxProduct(new int[]{2, 3, -2, 4});

        new Solution152().maxProduct(new int[]{0, 2});

        new Solution152().maxProduct(new int[]{-5, 0, 2});

    }
}

class Solution152 {

    /**
     * 思路：
     *
     * f_max(i) = max{ f_max(i - 1) * nums[i], f_min(i - 1) * nums[i], nums[i] }
     * f_min(i) = min{ f_max(i - 1) * nums[i], f_min(i - 1) * nums[i], nums[i] }
     *
     * @param nums
     * @return
     */
    public int maxProduct(int[] nums) {
        int max = nums[0], curMax = nums[0], curMin = nums[0], tMax;
        for (int i = 1; i < nums.length; i++) {
            tMax = Math.max(curMax * nums[i], Math.max(curMin * nums[i], nums[i]));
            max = Math.max(max, tMax);
            curMin = Math.min(curMax * nums[i], Math.min(curMin * nums[i], nums[i]));
            curMax = tMax;

        }
        return max;
    }

}
